#define _CRT_SECURE_NO_WARNINGS 1

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* cur1 = list1;
    struct ListNode* cur2 = list2;

    if (list1 == NULL && list2)return list2;
    if (list1 && list2 == NULL)return list1;
    if (list1 == NULL && !list2)return NULL;
    struct ListNode* newlist = NULL;
    struct ListNode* star = NULL;
    if (cur1->val < cur2->val) {
        newlist = cur1;
        //star=newlist;
        cur1 = cur1->next;
    }
    else {
        newlist = cur2;
        cur2 = cur2->next;
    }
    star = newlist;
    while (cur1) {
        while (cur2 && cur2->val <= cur1->val) {
            newlist->next = cur2;
            newlist = newlist->next;
            cur2 = cur2->next;
        }
        newlist->next = cur1;
        newlist = newlist->next;
        cur1 = cur1->next;
    }
    while (cur2) {
        newlist->next = cur2;
        newlist = newlist->next;
        cur2 = cur2->next;
    }

    return star;
}